
import { _decorator, Component, Node, Rect } from 'cc';
const { ccclass, property } = _decorator;


interface IQuadTreeOptions {
    maxObjects?: number;
    maxLevels?: number;
    level?: number;
    bounds: Rect;
}

@ccclass('QuadTree ')
export class QuadTree {
    objects: any[];
    nodes: QuadTree[];
    level: number;
    maxObjects: number;
    maxLevels: number;
    bounds: Rect;

    constructor(options: IQuadTreeOptions) {
        this.objects = [];
        this.nodes = [];
        this.level = options.level || 0;
        this.maxObjects = options.maxObjects || 10;
        this.maxLevels = options.maxLevels || 4;
        this.bounds = options.bounds;
    }

    clear() {
        this.objects = [];
        for (let i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i]) {
                this.nodes[i].clear();
                delete this.nodes[i];
            }
        }
        this.nodes = [];
    }

    split() {
        const subWidth = this.bounds.width / 2;
        const subHeight = this.bounds.height / 2;
        const x = this.bounds.x;
        const y = this.bounds.y;

        this.nodes[0] = new QuadTree({
            level: this.level + 1,
            bounds: new Rect(x + subWidth, y, subWidth, subHeight),
            maxObjects: this.maxObjects,
            maxLevels: this.maxLevels,
        });
        this.nodes[1] = new QuadTree({
            level: this.level + 1,
            bounds: new Rect(x, y, subWidth, subHeight),
            maxObjects: this.maxObjects,
            maxLevels: this.maxLevels,
        });
        this.nodes[2] = new QuadTree({
            level: this.level + 1,
            bounds: new Rect(x, y + subHeight, subWidth, subHeight),
            maxObjects: this.maxObjects,
            maxLevels: this.maxLevels,
        });
        this.nodes[3] = new QuadTree({
            level: this.level + 1,
            bounds: new Rect(x + subWidth, y + subHeight, subWidth, subHeight),
            maxObjects: this.maxObjects,
            maxLevels: this.maxLevels,
        });
    }

    getIndex(rect: Rect) {
        const midPointX = this.bounds.x + this.bounds.width / 2;
        const midPointY = this.bounds.y + this.bounds.height / 2;
        const topQuadrant = rect.y >= midPointY;
        const bottomQuadrant = rect.y + rect.height < midPointY;
        let index = -1;

        if (rect.x + rect.width < midPointX) {
            if (topQuadrant) {
                index = 1;
            } else if (bottomQuadrant) {
                index = 2;
            }
        } else if (rect.x >= midPointX) {
            if (topQuadrant) {
                index = 0;
            } else if (bottomQuadrant) {
                index = 3;
            }
        }

        return index;
    }

    insert(rect) {
        if (this.nodes.length) {
            let index = this.getIndex(rect);

            if (index !== -1) {
                this.nodes[index].insert(rect);

                return;
            }
        }

        this.objects.push(rect);

        if (this.objects.length > this.maxObjects && this.level < this.maxLevels) {
            if (!this.nodes.length) {
                this.split();
            }

            let i = 0;

            while (i < this.objects.length) {
                let index = this.getIndex(this.objects[i]);

                if (index !== -1) {
                    this.nodes[index].insert(this.objects.splice(i, 1)[0]);
                }
                else {
                    i++;
                }
            }
        }
    }

    retrieve(rect) {
        let foundObjects = [];

        if (this.nodes.length) {
            let index = this.getIndex(rect);

            if (index !== -1) {
                foundObjects = foundObjects.concat(this.nodes[index].retrieve(rect));
            }
            else {
                for (let i = 0; i < this.nodes.length; i++) {
                    foundObjects = foundObjects.concat(this.nodes[i].retrieve(rect));
                }
            }
        }

        foundObjects = foundObjects.concat(this.objects);

        return foundObjects;
    }
}
